/*
方法	    时间复杂度	空间复杂度	
find()   	O(n²)	    O(h)--递归调用栈的深度是树的高度 h		
哈希表加速	O(n)	    O(n)		
*/

//1.递归--find写法
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        int preindex = 0; // 当前构造的根节点在 preorder 中的位置
        return build(preorder, inorder, 0, inorder.size(), preindex);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder,
                    int begin, int end, int& preindex) {

        if (begin >= end) return nullptr;

        int root_val = preorder[preindex++];
        TreeNode* root = new TreeNode(root_val);
        int mid = find(inorder.begin(), inorder.end(), root_val) - inorder.begin();

        root->left = build(preorder, inorder, begin, mid, preindex);
        root->right = build(preorder, inorder, mid + 1, end, preindex);

        return root;
    }
};


//2.递归--哈希表写法
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 构建哈希表，加速中序查找
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i; // 值：索引
        }

        int preindex = 0; // 当前构造的根节点在 preorder 中的位置
        return build(preorder, inorder_map, 0, inorder.size(), preindex);  //左闭右开
    }

    TreeNode* build(vector<int>& preorder, unordered_map<int, int>& inorder_map,
                    int begin, int end, int& preindex) {

        if (begin >= end) return nullptr;

        int root_val = preorder[preindex++];
        TreeNode* root = new TreeNode(root_val);

        int mid = inorder_map.at(root_val); // 找到中序中根节点的位置
        //int mid = inorder_map[root_val]; // 
        root->left = build(preorder, inorder_map, begin, mid, preindex);
        root->right = build(preorder, inorder_map, mid + 1, end, preindex);

        return root;
    }
};



//3.迭代了解